package listbyorder.access001_100.test23;

import listbyorder.utils.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/29 15:08
 */
public class Solution3 {

    // 优先级队列
    public ListNode mergeKLists(ListNode[] lists) {
        //定义优先队列的比较器
        Comparator<ListNode> cmp;
        cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                // TODO Auto-generated method stub
                return o1.val-o2.val;
            }
        };

        //建立队列
        Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
        for(ListNode l : lists){
            if(l!=null){
                q.add(l);
            }
        }
        ListNode head = new ListNode(0);
        ListNode point = head;
        while(!q.isEmpty()){
            //出队列
            point.next = q.poll();
            point = point.next;
            //判断当前链表是否为空，不为空就将新元素入队
            ListNode next = point.next;
            if(next!=null){
                q.add(next);
            }
        }
        return head.next;
    }

}
